package com.zwj.interview.链表;

import com.zwj.interview.链表.ListNode;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 输入k个排序的链表，请将它们合并成一个排序的链表
 */
public class MergeKSortedLinkedList {

    /**
     * 使用最小堆的思路：
     * 用k个指针分别指向这k个链表的头节点，每次从这k个节点中选取值最小的节点。
     * 然后将指向值最小的节点的指针向后移动一步，再比较k个指针指向的节点并选取值最小的节点。
     * 重复这个过程，直到所有节点都被选取出来
     * <p>
     * <p>
     * 这种思路需要反复比较k个节点并选取值最小的节点。既可以每次都用一个for循环用O（k）的时间复杂度比较k个节点的值，
     * 也可以将k个节点放入一个最小堆中，位于堆顶的节点就是值最小的节点。每当选取某个值最小的节点之后，
     * 将它从堆中删除并将它的下一个节点添加到堆中。从最小堆中得到位于堆顶的节点的时间复杂度是O（1），
     * 堆的删除和插入操作的时间复杂度是O（logk），因此使用最小堆比直观地用for循环的时间效率更高
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        //使用最小堆的思路
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
        //先往堆里把每个链表的头节点添入到最小堆中
        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }
        //每次弹出堆顶的元素，这个元素就是最小的元素，然后再把弹出元素的next节点放入堆中
        while (!minHeap.isEmpty()) {
            ListNode least = minHeap.poll();
            //当前节点的next指针指向堆顶弹出的元素
            cur.next = least;
            if (least.next != null) {
                minHeap.offer(least.next);
            }
            //往下移动cur指针
            cur = cur.next;
        }
        return dummy.next;
    }





}
